package leetcode.p494;

/**
 * @author: trtan
 * @date: 2021-06-07 08:45
 **/
public class TargetSum {
    public static void main(String[] args) {
        int[] array = new int[]{26,15,38,20,40,10,14,35,32,20,7,18,38,6,46,46,20,50,35,41};
        System.out.println(new TargetSum().findTargetSumWays(array, 3));
    }

    int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 0, target, 0);
    }

    int dfs(int[] arrays, int depth, int target, int sum) {
        if (depth == arrays.length) {
            if (target == sum) {
                return 1;
            } else {
                return 0;
            }
        }
        int result = 0;
        result += dfs(arrays, depth + 1, target, sum + arrays[depth]);
        result += dfs(arrays, depth + 1, target, sum - arrays[depth]);
        return result;
    }
}
